package solutions.jianzhi;

import solutions.lib.BaseSolution;
import solutions.lib.ListNode;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/3u1WK4/">剑指 Offer II 023. 两个链表的第一个重合节点</a>
 */
public class Solution23 extends BaseSolution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lenA = 0;
        ListNode p = headA;
        while (p != null) {
            lenA++;
            p = p.next;
        }
        int lenB = 0;
        p = headB;
        while (p != null) {
            lenB++;
            p = p.next;
        }

        while (lenA != lenB) {
            if (lenA > lenB) {
                lenA--;
                headA = headA.next;
            } else {
                lenB--;
                headB = headB.next;
            }
        }
        while (headA != null && headB != null && headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }

    public static void main(String[] args) {
        Solution23 solution = new Solution23();
    }
}